{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Distribute Candies"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: distributeCandies"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #分糖果"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>Alice 有 <code>n</code> 枚糖，其中第 <code>i</code> 枚糖的类型为 <code>candyType[i]</code> 。Alice 注意到她的体重正在增长，所以前去拜访了一位医生。</p>\n",
    "\n",
    "<p>医生建议 Alice 要少摄入糖分，只吃掉她所有糖的 <code>n / 2</code> 即可（<code>n</code> 是一个偶数）。Alice 非常喜欢这些糖，她想要在遵循医生建议的情况下，尽可能吃到最多不同种类的糖。</p>\n",
    "\n",
    "<p>给你一个长度为 <code>n</code> 的整数数组 <code>candyType</code> ，返回： Alice <em>在仅吃掉 <code>n / 2</code> 枚糖的情况下，可以吃到糖的 <strong>最多</strong> 种类数</em>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>candyType = [1,1,2,2,3,3]\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>Alice 只能吃 6 / 2 = 3 枚糖，由于只有 3 种糖，她可以每种吃一枚。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>candyType = [1,1,2,3]\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>Alice 只能吃 4 / 2 = 2 枚糖，不管她选择吃的种类是 [1,2]、[1,3] 还是 [2,3]，她只能吃到两种不同类的糖。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>candyType = [6,6,6,6]\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>Alice 只能吃 4 / 2 = 2 枚糖，尽管她能吃 2 枚，但只能吃到 1 种糖。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == candyType.length</code></li>\n",
    "\t<li><code>2 &lt;= n &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>n</code> 是一个偶数</li>\n",
    "\t<li><code>-10<sup>5</sup> &lt;= candyType[i] &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [distribute-candies](https://leetcode.cn/problems/distribute-candies/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [distribute-candies](https://leetcode.cn/problems/distribute-candies/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,1,2,2,3,3]', '[1,1,2,3]', '[6,6,6,6]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, n: int, limit: int) -> int:\n",
    "        if limit > n:\n",
    "            return math.comb(n+2, 2)\n",
    "        \n",
    "        @cache\n",
    "        def dp(i, k):\n",
    "            if k == 0:\n",
    "                return min(i, limit) - max(0, i - limit) + 1\n",
    "            \n",
    "            ans = 0\n",
    "            for j in reversed(range(limit+1)):\n",
    "                if i - j > 2 * limit: break\n",
    "                ans += dp(i - j, k - 1)\n",
    "            return ans\n",
    "        \n",
    "        return dp(n, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, n: int, limit: int) -> int:\n",
    "        ans = 0\n",
    "        for i in range(n+1):\n",
    "            for j in range(n+1):\n",
    "                k = n - i - j\n",
    "                if k >= 0 and i <= limit and j <= limit and k <= limit:\n",
    "                    ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, n: int, limit: int) -> int:\n",
    "        ans = 0\n",
    "        for i in range(limit+1):\n",
    "            for j in range(limit+1):\n",
    "                for k in range(limit+1):\n",
    "                    if i+j+k == n:\n",
    "                        ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def distributeCandies(self, n: int, limit: int) -> int:\r\n",
    "        return self.solve2(n, limit)\r\n",
    "    \"\"\"\r\n",
    "        1. Brute Force\r\n",
    "    \"\"\"\r\n",
    "    def solve1(self, n: int, limit: int) -> int:\r\n",
    "        ans = 0\r\n",
    "        for i in range(limit+1):\r\n",
    "            for j in range(limit+1):\r\n",
    "                k = n - i - j\r\n",
    "                if k >= 0 and k <= limit:\r\n",
    "                    ans += 1\r\n",
    "        return ans\r\n",
    "    \"\"\"\r\n",
    "        2. 排容原理\r\n",
    "        a. 所有方案數：\r\n",
    "            H(3, n) = C(n+2, n) = C(n+2, 2)\r\n",
    "        b. 至少一人拿到超過 limit 個糖果的方案數：\r\n",
    "            (先分(limit+1)給他，剩下的分給所有人)\r\n",
    "            3 * H(3, n-(limit+1)) = 3 * C(n−(limit+1)+2, 2)\r\n",
    "        c. 至少兩人拿到超過 limit 個糖果的方案數：\r\n",
    "            3 * C(n−2⋅(limit+1)+2, 2)\r\n",
    "    \"\"\"\r\n",
    "\r\n",
    "    def solve2(self, n: int, limit: int) -> int:\r\n",
    "        if n > 3 * limit: # 三人都拿到超過 limit 個糖果，沒有方案\r\n",
    "            return 0\r\n",
    "        ans = comb(n + 2, 2)\r\n",
    "        if n >= (limit + 1): # 至少一人拿到超過 limit 個糖果\r\n",
    "            ans -= 3 * comb(n - limit + 1, 2)\r\n",
    "        if n >= 2 * (limit + 1): # 至少兩人拿到超過 limit 個糖果\r\n",
    "            ans += 3 * comb(n - 2 * limit, 2)\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, n: int, limit: int) -> int:\n",
    "        @cache\n",
    "        def f(i,n):\n",
    "            if i==2 or n<0:\n",
    "                if n>=0 and n<=limit:\n",
    "                    return 1\n",
    "                return 0\n",
    "            m=0\n",
    "            for j in range(limit+1):\n",
    "                m+=f(i+1,n-j)\n",
    "            return m\n",
    "        return f(0,n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, n: int, limit: int) -> int:\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(0, min(n, limit)+1):\n",
    "            ans += max(0, min(limit, n - i) - max(0, n - i - limit) + 1)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def c2(n):\n",
    "    return n * (n - 1) // 2 if n > 1 else 0\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, n: int, limit: int) -> int:\n",
    "        return c2(n + 2) - 3 * c2(n - limit + 1) + 3 * c2(n - 2 * limit) - c2(n - 3 * limit - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def distributeCandies(self, n: int, limit: int) -> int:\r\n",
    "        return self.solve2(n, limit)\r\n",
    "    \"\"\"\r\n",
    "        1. Brute Force\r\n",
    "    \"\"\"\r\n",
    "    def solve1(self, n: int, limit: int) -> int:\r\n",
    "        ans = 0\r\n",
    "        for i in range(limit+1):\r\n",
    "            for j in range(limit+1):\r\n",
    "                k = n - i - j\r\n",
    "                if k >= 0 and k <= limit:\r\n",
    "                    ans += 1\r\n",
    "        return ans\r\n",
    "    \"\"\"\r\n",
    "        2. 排容原理\r\n",
    "        a. 所有方案數：\r\n",
    "            H(3, n) = C(n+2, n) = C(n+2, 2)\r\n",
    "        b. 至少一人拿到超過 limit 個糖果的方案數：\r\n",
    "            (先分(limit+1)給他，剩下的分給所有人)\r\n",
    "            3 * H(3, n-(limit+1)) = 3 * C(n−(limit+1)+2, 2)\r\n",
    "        c. 至少兩人拿到超過 limit 個糖果的方案數：\r\n",
    "            3 * C(n−2⋅(limit+1)+2, 2)\r\n",
    "    \"\"\"\r\n",
    "\r\n",
    "    def solve2(self, n: int, limit: int) -> int:\r\n",
    "        if n > 3 * limit: # 三人都拿到超過 limit 個糖果，沒有方案\r\n",
    "            return 0\r\n",
    "        ans = comb(n + 2, 2)\r\n",
    "        if n >= (limit + 1): # 至少一人拿到超過 limit 個糖果\r\n",
    "            ans -= 3 * comb(n - limit + 1, 2)\r\n",
    "        if n >= 2 * (limit + 1): # 至少兩人拿到超過 limit 個糖果\r\n",
    "            ans += 3 * comb(n - 2 * limit, 2)\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, n: int, limit: int) -> int:\n",
    "        dp = list()\n",
    "        for i in range(min(n + 1, limit + 1)):\n",
    "            dp.append(i + 1)\n",
    "        x = limit + 1\n",
    "        while n >= x and x <= 2 * limit:\n",
    "            dp.append(2 * limit - x + 1)\n",
    "            x += 1\n",
    "        ans = 0\n",
    "        # print(dp)\n",
    "        for i in range(min(n + 1, limit + 1)):\n",
    "            if n <= 2 * limit + i:\n",
    "                ans += dp[n - i]\n",
    "        return ans \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, n: int, limit: int) -> int:\n",
    "        if 3 * limit < n:\n",
    "            return 0\n",
    "        cnt = [0] * (n + 1)\n",
    "        for i in range(min(n, 2 * limit) + 1):\n",
    "            if i > limit:\n",
    "                cnt[i] = 2 * limit - i + 1\n",
    "            else:\n",
    "                cnt[i] = i + 1\n",
    "        return sum(cnt[i] for i in range(n + 1) if n - i <= limit)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, n: int, limit: int) -> int:\n",
    "        \n",
    "#         @lru_cache(None)\n",
    "#         def dfs(i,j):\n",
    "#             if (3 - i) * limit < j:return 0\n",
    "#             if j == 0:return 1\n",
    "#             if i == 1:return max(0,min(limit,j) - max(0,(j - limit)) + 1)\n",
    "#             if i == 2:return j <= limit\n",
    "#             ans = 0\n",
    "#             for k in range(limit+1):\n",
    "#                 if k > j:break\n",
    "#                 ans += dfs(i+1,j-k)\n",
    "#             return ans\n",
    "        \n",
    "#         return dfs(0,n)\n",
    "    \n",
    "        dp = [[0 for _ in range(n+2)] for _ in range(5)]\n",
    "        for i in range(5):\n",
    "            dp[i][0] = 1\n",
    "        ans = 0\n",
    "        for j in range(max(0,n-limit),n+1):\n",
    "            if 2 * limit < j:\n",
    "                dp[1][j] = 0\n",
    "                break\n",
    "            # dp[1][j] = max(0,min(limit,j) - max(0,(j-limit)) + 1)\n",
    "            ans += max(0,min(limit,j) - max(0,(j-limit)) + 1)\n",
    "        return ans\n",
    "\n",
    "        # ans = 0\n",
    "        # if n <= limit:\n",
    "        #     for k in range(n+1):\n",
    "        #         ans += dp[1][n-k]\n",
    "        # else:\n",
    "        #     for k in range(limit+1):\n",
    "        #         ans += dp[1][n-k]\n",
    "        # return ans     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, n: int, limit: int) -> int:\n",
    "        ans = 0\n",
    "        for k in range(8):\n",
    "            t = bin(k).count('1')\n",
    "            rem = n - (limit + 1) * t\n",
    "            if rem < 0:\n",
    "                continue\n",
    "            ans += pow(-1, t) * comb(rem + 2, 2)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def c2(n: int) -> int:\n",
    "    return n*(n-1)//2 if n>1 else 0\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, n: int, limit: int) -> int:\n",
    "        return c2(n+2)-3*c2(n-limit+1)+3*c2(n-2*limit)-c2(n-3*limit-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, n: int, limit: int) -> int:\n",
    "        if n > 3 * limit:\n",
    "            return 0\n",
    "        ans = comb(n + 2, 2)\n",
    "        if n > limit:\n",
    "            ans -= 3 * comb(n - limit + 1, 2)\n",
    "        if n - 2 >= 2 * limit:\n",
    "            ans += 3 * comb(n - 2 * limit, 2)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, n: int, limit: int) -> int:\n",
    "        if n > 3 * limit:\n",
    "            return 0\n",
    "        ans = comb(n + 2, 2)\n",
    "        if n > limit:\n",
    "            ans -= 3 * comb(n - limit + 1, 2)\n",
    "        if n - 2 >= 2 * limit:\n",
    "            ans += 3 * comb(n - 2 * limit, 2)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, n: int, limit: int) -> int:\n",
    "                return (math.comb(n + 2, 2) - (3 * math.comb(max(n - (limit + 1) + 2, 0), 2) \n",
    "                                       - 3 * math.comb(max(n - 2 * (limit + 1) + 2, 0), 2) \n",
    "                                       + math.comb(max(n - 3 * (limit + 1) + 2, 0), 2)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def c2(n: int) -> int:\n",
    "    return n * (n - 1) // 2 if n > 1 else 0\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, n: int, limit: int) -> int:\n",
    "        return c2(n + 2) - 3 * c2(n - limit + 1) + 3 * c2(n - 2 * limit) - c2(n - 3 * limit - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, n: int, limit: int) -> int:\n",
    "        def cal(a, b):\n",
    "            if a < b:\n",
    "                return 0\n",
    "            return comb(a, b)\n",
    "        \n",
    "        return cal(n + 2, 2) - 3 * cal(n - limit + 1, 2) + 3 * cal(n - 2 * limit, 2) - cal(n - 3 * limit - 1, 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def c2(n: int) -> int:\n",
    "    return n * (n - 1) // 2 if n > 1 else 0\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, n: int, limit: int) -> int:\n",
    "        return c2(n + 2) - 3 * c2(n - limit + 1) + 3 * c2(n - 2 * limit) - c2(n - 3 * limit - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, n: int, limit: int) -> int:\n",
    "        def c(n):\n",
    "            if n < 2:\n",
    "                return 0\n",
    "            return comb(n, 2)\n",
    "        return comb(n + 2, 2) - 3 * c(n - (limit + 1) + 2) + 3 * c(n - 2 * (limit + 1) + 2) - c(n - 3 * (limit + 1) + 2)\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, n: int, limit: int) -> int:\n",
    "        def c(n):\n",
    "            if n < 2:\n",
    "                return 0\n",
    "            return comb(n, 2)\n",
    "        return comb(n + 2, 2) - 3 * c(n - (limit + 1) + 2) + 3 * c(n - 2 * (limit + 1) + 2) - c(n - 3 * (limit + 1) + 2)\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def C2(n: int) -> int:\n",
    "    if n <= 1:\n",
    "        return 0\n",
    "    return n * (n - 1) // 2\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, n: int, limit: int) -> int:\n",
    "        res0 = C2(n + 2)  # 总方案数,x1+x2+x3=n的非负整数解的个数(隔板法)\n",
    "        res1 = 3 * C2(n + 2 - (limit + 1))  # 至少一个小朋友分到的糖果超过 limit 的方案数\n",
    "        res2 = 3 * C2(n + 2 - 2 * (limit + 1))  # 至少两个小朋友分到的糖果超过 limit\n",
    "        res3 = C2(n + 2 - 3 * (limit + 1))  # 三个小朋友分到的糖果都超过 limit\n",
    "        return res0 - res1 + res2 - res3\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def c2(n: int) -> int:\n",
    "    return n * (n - 1) // 2 if n > 1 else 0\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, n: int, limit: int) -> int:\n",
    "        return c2(n + 2) - 3 * c2(n - limit + 1) + 3 * c2(n - 2 * limit) - c2(n - 3 * limit - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, n: int, limit: int) -> int:\n",
    "        ans = 0\n",
    "        for k in range(8):\n",
    "            t = k.bit_count()\n",
    "            rem = n - (limit + 1) * t\n",
    "            if rem >= 0:\n",
    "                ans += pow(-1, t) * comb(rem + 2, 2)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, n: int, limit: int) -> int:\n",
    "            \n",
    "        def helper(num):\n",
    "            if num < 0:\n",
    "                return 0\n",
    "            return (num + 2) * (num + 1) // 2\n",
    "\n",
    "        return helper(n) - (3 * helper(n - limit - 1) - 3 * helper(n - 2 * limit - 2) + helper(n - 3 * limit - 3))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# def c2(n: int) -> int:\n",
    "#     return n * (n - 1) // 2 if n > 1 else 0\n",
    "\n",
    "# class Solution:\n",
    "#     def distributeCandies(self, n: int, limit: int) -> int:\n",
    "#         print(c2(n + 2), c2(n - limit + 1), 3 * c2(n - 2 * limit), c2(n - 3 * limit - 1))\n",
    "#         return c2(n + 2) - 3 * c2(n - limit + 1) + 3 * c2(n - 2 * limit) - c2(n - 3 * limit - 1)\n",
    "\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def distributeCandies(self, n: int, lim: int) -> int:\n",
    "        \n",
    "        co = math.comb \n",
    "        # def co(n, y) -> int:\n",
    "        #     return n * (n - 1) // 2 if n > 1 else 0\n",
    "        all = co(n + 3 - 1, 2) \n",
    "        if n<=lim:\n",
    "            a = 0 \n",
    "        else:\n",
    "            res = (n - 1 - lim) \n",
    "            a = co(res + 3 - 1, 2)\n",
    "        b = a \n",
    "        c = a \n",
    "        if n<(2*lim + 2):\n",
    "            d = 0 \n",
    "        else:\n",
    "            res = n-2-2*lim \n",
    "            d = co(res + 3 - 1, 2) \n",
    "        e = d \n",
    "        f = d \n",
    "        if n<(3*lim + 3):\n",
    "            g = 0 \n",
    "        else:\n",
    "            res = n-3-3*lim \n",
    "            g = co(res+3-1, 2) \n",
    "        # print(all, a, d, g)\n",
    "        return all - (a+b+c-d-e-f+g)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, n: int, limit: int) -> int:\n",
    "        if n > limit*3: return 0\n",
    "        hi = n-max(0,n-2*limit)\n",
    "        lo = max(0,n-limit)\n",
    "        def calc(x):\n",
    "            return min(limit,x)-max(0,x-limit)+1\n",
    "        def calc2(mi,mx):\n",
    "            return (mi+mx)*(mx-mi+1)//2\n",
    "        # print(lo,hi)\n",
    "        if hi <= limit:\n",
    "            return calc2(calc(lo),calc(hi))\n",
    "        elif lo >= limit:\n",
    "            return calc2(calc(hi),calc(lo))\n",
    "        else:\n",
    "            return calc2(calc(lo),calc(limit))+calc2(calc(hi),calc(limit))-limit-1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def c2(n: int) -> int:\n",
    "    return n * (n - 1) // 2 if n > 1 else 0\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, n: int, limit: int) -> int:\n",
    "        return c2(n + 2) - 3 * c2(n - limit + 1) + 3 * c2(n - 2 * limit) - c2(n - 3 * limit - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def check(x):\n",
    "    if x <= 1:\n",
    "        return 0\n",
    "    return x*(x-1)//2\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, n: int, limit: int) -> int:\n",
    "        return check(n+2) - 3*check(n-limit+1) + 3*check(n-2*limit) - check(n-3*limit-1)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        ans=[0 for i in range(num_people)]\n",
    "        i=0\n",
    "        while candies>0:\n",
    "            ans[i%num_people]=ans[i%num_people]+min(i+1,candies)\n",
    "            i+=1\n",
    "            candies=max(0,candies-i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        res = [0] * num_people\n",
    "        index = 0\n",
    "        while candies:\n",
    "            people = index % num_people\n",
    "            cadit = index + 1\n",
    "            if candies >= cadit:\n",
    "                res[people] += cadit\n",
    "                candies -= cadit\n",
    "            else:\n",
    "                res[people] += candies\n",
    "                candies = 0\n",
    "            index += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        ans = [0] * num_people\n",
    "        i = 0\n",
    "        while candies != 0:\n",
    "            ans[i % num_people] += min(i + 1, candies)\n",
    "            candies -= min(i + 1, candies)\n",
    "            i += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        kids = [0]*num_people\n",
    "        i = 0\n",
    "        while candies>0:\n",
    "            kids[i%num_people] += min(i+1,candies)\n",
    "            candies -= i +1\n",
    "            i+=1\n",
    "        return kids"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        total = 0\n",
    "        index = 1\n",
    "        ls = [0] * num_people\n",
    "        while total < candies:\n",
    "            _index = index % num_people - 1\n",
    "            if total + index > candies:\n",
    "                ls[_index] += candies - total\n",
    "            else:\n",
    "                ls[_index] += index\n",
    "            total += index\n",
    "            index += 1\n",
    "\n",
    "        return ls\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        n = num_people\n",
    "        m = int((sqrt(8 * candies + 1) - 1) / (2 * n))\n",
    "        nm = n * m\n",
    "        answer = [(1+i) * m + nm * (m-1) // 2 for i in range(n)]\n",
    "        candies -= (1 + nm) * nm // 2\n",
    "        i = 0\n",
    "        while candies > 0:\n",
    "            c = min(nm + 1 + i, candies)\n",
    "            answer[i] += c\n",
    "            candies -= c\n",
    "            i = (i+1) % n\n",
    "        return answer\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        nums=[0]*num_people\n",
    "        con=0\n",
    "        cur=0\n",
    "        i=0\n",
    "        while con<candies:\n",
    "            if con+cur+1>candies:\n",
    "                nums[i]+=candies-con\n",
    "            else:\n",
    "                nums[i]+=cur+1\n",
    "            con+=cur+1\n",
    "            cur+=1\n",
    "            i+=1\n",
    "            i%=num_people\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        ans = [0] * num_people\n",
    "        i = 0\n",
    "        while candies != 0:\n",
    "            ans[i % num_people] += min(i + 1, candies)\n",
    "            candies -= min(i + 1, candies)\n",
    "            i += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        tmp = [0 for i in range(num_people)]\n",
    "        sum = 1\n",
    "        while candies:\n",
    "            for n in range(num_people):\n",
    "                if candies >=sum:\n",
    "                    tmp[n]+=sum\n",
    "                    candies-=sum\n",
    "                    sum+=1\n",
    "                else:\n",
    "                    tmp[n]+=candies\n",
    "                    candies = 0\n",
    "                    break\n",
    "        return tmp\n",
    "\n",
    "\n",
    "            \n",
    "                \n",
    "\n",
    "                \n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        ans=[0]*num_people\n",
    "        i=0\n",
    "        while candies:\n",
    "            if candies-(i+1)>=0:\n",
    "                ans[i%num_people]+=i+1\n",
    "                candies-=i+1\n",
    "            else:\n",
    "                ans[i%num_people]+=candies\n",
    "                candies=0\n",
    "            i+=1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        list_,a,b=[0 for _ in range(num_people)],0,0\n",
    "        while True:\n",
    "            b+=1\n",
    "            if candies>=b:\n",
    "                list_[a]+=b\n",
    "            else:\n",
    "                b=candies\n",
    "                list_[a]+=b\n",
    "            candies-=b\n",
    "            a+=1\n",
    "            if candies==0:\n",
    "                return list_\n",
    "            if a==num_people:\n",
    "                a=0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "#         ans=[0]*num_people\n",
    "#         i=0\n",
    "#         while candies:\n",
    "#             if candies-(i+1)>=0:\n",
    "#                 ans[i%num_people]+=i+1\n",
    "#                 candies-=i+1\n",
    "#             else:\n",
    "#                 ans[i%num_people]+=candies\n",
    "#                 candies=0\n",
    "#             i+=1\n",
    "#         return ans\n",
    "\n",
    "# ### 官1：暴力\n",
    "# class Solution:\n",
    "#     def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "#         ans = [0] * num_people\n",
    "#         i = 0\n",
    "#         while candies != 0:\n",
    "#             ans[i % num_people] += min(i + 1, candies)\n",
    "#             candies -= min(i + 1, candies)\n",
    "#             i += 1\n",
    "#         return ans\n",
    "\n",
    "##官2：等差数列\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        n = num_people\n",
    "        # how many people received complete gifts\n",
    "        p = int((2 * candies + 0.25)**0.5 - 0.5) \n",
    "        remaining = int(candies - (p + 1) * p * 0.5)\n",
    "        rows, cols = p // n, p % n\n",
    "        \n",
    "        d = [0] * n\n",
    "        for i in range(n):\n",
    "            # complete rows\n",
    "            d[i] = (i + 1) * rows + int(rows * (rows - 1) * 0.5) * n\n",
    "            # cols in the last row\n",
    "            if i < cols:\n",
    "                d[i] += i + 1 + rows * n\n",
    "        # remaining candies        \n",
    "        d[cols] += remaining\n",
    "        return d\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        full_groups=int(sqrt(2*candies+0.25)-0.5)\n",
    "        remain=candies-full_groups*(full_groups+1)//2\n",
    "        round=full_groups//num_people\n",
    "        round_candy_base=round+round*(round-1)//2*num_people\n",
    "        result=[round_candy_base+x*round for x in range(num_people)]\n",
    "        full_groups=full_groups%num_people\n",
    "        for i in range(full_groups):\n",
    "            result[i]+=round*num_people+1+i\n",
    "        result[full_groups]+=remain\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        candyNum = [0] * num_people\n",
    "        n = 0\n",
    "        while True:\n",
    "            i = n % num_people\n",
    "            candyNum[i] += min(n + 1, candies)\n",
    "            n += 1\n",
    "            candies -= n\n",
    "            if candies <= 0 or candyNum[-1] == 2 * num_people:\n",
    "                break\n",
    "\n",
    "        return candyNum\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        ans = [0] * num_people\n",
    "        i = 0\n",
    "        while candies != 0:\n",
    "            ans[i % num_people] += min(i + 1, candies)\n",
    "            candies -= min(i + 1, candies)\n",
    "            i += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        res = [0] * num_people\n",
    "        i = 0\n",
    "        while candies > 0:\n",
    "            res[i%num_people] += min(candies, i+1)\n",
    "            candies -= min(candies, i+1)\n",
    "            i += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "#         ans=[0]*num_people\n",
    "#         i=0\n",
    "#         while candies:\n",
    "#             if candies-(i+1)>=0:\n",
    "#                 ans[i%num_people]+=i+1\n",
    "#                 candies-=i+1\n",
    "#             else:\n",
    "#                 ans[i%num_people]+=candies\n",
    "#                 candies=0\n",
    "#             i+=1\n",
    "#         return ans\n",
    "\n",
    "# ### 官1：暴力\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        ans = [0] * num_people\n",
    "        i = 0\n",
    "        while candies != 0:\n",
    "            ans[i % num_people] += min(i + 1, candies)\n",
    "            candies -= min(i + 1, candies)\n",
    "            i += 1\n",
    "        return ans\n",
    "\n",
    "# ##官2：等差数列\n",
    "# class Solution:\n",
    "#     def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "#         n = num_people\n",
    "#         # how many people received complete gifts\n",
    "#         p = int((2 * candies + 0.25)**0.5 - 0.5) \n",
    "#         remaining = int(candies - (p + 1) * p * 0.5)\n",
    "#         rows, cols = p // n, p % n\n",
    "        \n",
    "#         d = [0] * n\n",
    "#         for i in range(n):\n",
    "#             # complete rows\n",
    "#             d[i] = (i + 1) * rows + int(rows * (rows - 1) * 0.5) * n\n",
    "#             # cols in the last row\n",
    "#             if i < cols:\n",
    "#                 d[i] += i + 1 + rows * n\n",
    "#         # remaining candies        \n",
    "#         d[cols] += remaining\n",
    "#         return d\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        '(a1+an)n/2。'\n",
    "        'na1+n(n-1)d/2'\n",
    "        circulation = 0\n",
    "        for i in range(1, candies):\n",
    "            if i + i * (i - 1) / 2 >= candies:\n",
    "                circulation = i\n",
    "                break\n",
    "        print(\"circulation\", circulation)\n",
    "\n",
    "        ls = [0] * num_people\n",
    "        _max = 0\n",
    "        for i in range(1, circulation + 1):\n",
    "            print(\"i\", i)\n",
    "            index = i % num_people - 1\n",
    "            if _max + i > candies:\n",
    "                ls[index] += candies - _max\n",
    "                return ls\n",
    "            ls[index] += i\n",
    "            _max += i\n",
    "        return ls\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        tmp = [0]*num_people\n",
    "        sum = 1\n",
    "        while candies:\n",
    "            for n in range(num_people):\n",
    "                if candies >=sum:\n",
    "                    tmp[n]+=sum\n",
    "                    candies-=sum\n",
    "                    sum+=1\n",
    "                else:\n",
    "                    tmp[n]+=candies\n",
    "                    candies = 0\n",
    "                    break\n",
    "        return tmp\n",
    "\n",
    "\n",
    "            \n",
    "                \n",
    "\n",
    "                \n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        result=[0]*num_people\n",
    "        num=0\n",
    "        while candies>0:\n",
    "            for i in range(num_people):\n",
    "                num+=1\n",
    "                if num<=candies:\n",
    "                    result[i]+=num\n",
    "                    candies=candies-num\n",
    "                else:\n",
    "                    result[i]+=candies\n",
    "                    candies=0\n",
    "                    break\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        ans=[0 for _ in range(num_people)]\n",
    "        n=1\n",
    "        while candies>0:\n",
    "            for i in range(num_people):\n",
    "                if candies>n:\n",
    "                    ans[i]=ans[i]+n\n",
    "                    candies=candies-n\n",
    "                    n+=1\n",
    "                else:\n",
    "                    ans[i]=ans[i]+candies\n",
    "                    candies=0\n",
    "            print(ans)\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        nums = [0]*num_people\n",
    "        k = 1\n",
    "        # flage = 0\n",
    "        while candies!=0:\n",
    "            for i in range(num_people):\n",
    "                if candies >= k:\n",
    "                    nums[i] += k\n",
    "                    candies -= k\n",
    "                    k += 1\n",
    "                else:\n",
    "                    nums[i] += candies\n",
    "                    candies -= candies\n",
    "                    # flage = 1\n",
    "                    break\n",
    "            # if candies == 0:\n",
    "            #     break\n",
    "        print(nums)\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        de = [0]*num_people\n",
    "        print(de)\n",
    "        s = 0\n",
    "        while s*(s+1) < 2*candies:\n",
    "            lun,duo = (s+1)//num_people,(s+1)%num_people\n",
    "            s += 1\n",
    "        print(lun,duo)\n",
    "        for i in range(lun):\n",
    "            for j in range(num_people):\n",
    "                de[j] += num_people*i+(j+1)\n",
    "        print(de)\n",
    "        if duo >= 1:\n",
    "            for i in range(duo-1):\n",
    "                de[i] += num_people*lun+(i+1)\n",
    "            re = int(candies - (lun*num_people+duo-1)*(lun*num_people+duo)/2)\n",
    "            de[duo-1] += re\n",
    "        else:\n",
    "            de[num_people-1] = int((lun-1)*(num_people*lun)/2)\n",
    "            re = int(candies - (lun*num_people+duo-1)*(lun*num_people+duo)/2)\n",
    "            de[num_people-1] += re\n",
    "        return de"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        ls = []\n",
    "        ls_count = []\n",
    "        for i in range(1,100000):\n",
    "\n",
    "            if candies - sum(ls) < i:\n",
    "                ls.append(candies - sum(ls))\n",
    "                break\n",
    "            else:\n",
    "                ls.append(i)\n",
    "        for j in range(num_people):\n",
    "            ls_count.append(sum(ls[j::num_people]))\n",
    "        return ls_count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        i = 1\n",
    "        res = []\n",
    "        while (1+i)*i//2 <= candies:\n",
    "            res.append(i)\n",
    "            i += 1\n",
    "        \n",
    "        if (i-1)*i//2 < candies:\n",
    "            res.append(candies-(i-1)*i//2)\n",
    "        \n",
    "        ans = [0]*num_people\n",
    "        for i in range(len(res)):\n",
    "            ans[i%num_people] += res[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        candies_list = []\n",
    "        i = 1\n",
    "        while candies > i:\n",
    "            candies_list.append(i)\n",
    "            candies -= i\n",
    "            i += 1\n",
    "        if  candies:\n",
    "            candies_list.append(candies)\n",
    "        ans = []\n",
    "        for  i in range(num_people):\n",
    "            ans.append(sum(candies_list[i::num_people]))\n",
    "        return ans\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        candies_list = []\n",
    "        i = 1\n",
    "        while candies > i:\n",
    "            candies_list.append(i)\n",
    "            candies -= i\n",
    "            i += 1\n",
    "        if  candies:\n",
    "            candies_list.append(candies)\n",
    "        ans = []\n",
    "        for  i in range(num_people):\n",
    "            ans.append(sum(candies_list[i::num_people]))\n",
    "        return ans\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        cand=[]\n",
    "        i=1\n",
    "        while candies>0:\n",
    "            if candies > i:\n",
    "                candies = candies - i\n",
    "                cand.append(i)\n",
    "                i += 1\n",
    "            else:\n",
    "                cand.append(candies)\n",
    "                break\n",
    "        ans=[]\n",
    "        for i in range(len(cand)):\n",
    "            if len(ans)< num_people and i<=num_people:\n",
    "                ans.append(cand[i])\n",
    "            else:\n",
    "                ans[i%num_people]=cand[i]+ans[i%num_people]\n",
    "        if len(ans)==num_people:\n",
    "            return ans\n",
    "        else:\n",
    "            for i in range (len(ans),num_people):\n",
    "                ans.append(0)\n",
    "            return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        candies_list = []\n",
    "        i = 1\n",
    "        while candies > i:\n",
    "            candies_list.append(i)\n",
    "            candies -= i\n",
    "            i += 1\n",
    "        if  candies:\n",
    "            candies_list.append(candies)\n",
    "        ans = []\n",
    "        for  i in range(num_people):\n",
    "            ans.append(sum(candies_list[i::num_people]))\n",
    "        return ans\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        candies_list = []\n",
    "        i = 1\n",
    "        while candies > i:\n",
    "            candies_list.append(i)\n",
    "            candies -= i\n",
    "            i += 1\n",
    "        if  candies:\n",
    "            candies_list.append(candies)\n",
    "        ans = []\n",
    "        for  i in range(num_people):\n",
    "            ans.append(sum(candies_list[i::num_people]))\n",
    "        return ans\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        res = []\n",
    "        num = []\n",
    "        result = [0] * num_people\n",
    "        i = 1\n",
    "        while candies > 0:\n",
    "            if candies >= i:\n",
    "                num.append(i)\n",
    "                candies -= i\n",
    "                if len(num) == num_people:\n",
    "                    res.append(num)\n",
    "                    num = []\n",
    "                if candies == 0:\n",
    "                    num += [0] * (num_people - len(num))\n",
    "                    res.append(num)\n",
    "                    break\n",
    "            else:\n",
    "                num.append(candies)\n",
    "                num += [0] * (num_people - len(num))\n",
    "                res.append(num)\n",
    "                break\n",
    "            i += 1\n",
    "        for k in range(num_people):\n",
    "            for j in range(len(res)):\n",
    "                result[k] += res[j][k]\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "\n",
    "        from collections import defaultdict\n",
    "        import logging\n",
    "        dic = defaultdict(int)\n",
    "        x=1\n",
    "        while candies>0:\n",
    "            for i in range(num_people):\n",
    "                if candies>x:\n",
    "                    dic[i]+=x\n",
    "                    candies-=x\n",
    "                else:\n",
    "                    dic[i]+=candies\n",
    "                    candies=0\n",
    "                    break\n",
    "                x+=1\n",
    "        result=[]\n",
    "        for i in range(num_people):\n",
    "            result.append(dic[i])\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        candies_tmp = int((8*candies + 1)**0.5/2 - 0.5)\n",
    "        new_candies = list(range(1,candies_tmp+1))\n",
    "        new_candies.append(candies - sum(new_candies))\n",
    "        res = [0]*num_people\n",
    "        idx = 0\n",
    "        for i in new_candies:\n",
    "            res[idx%num_people] += i\n",
    "            idx += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        ans = [0] * num_people\n",
    "        n = int( math.sqrt(2 * candies))\n",
    "        r = candies - n * (n+1)//2\n",
    "        if r < 0:\n",
    "            n-=1\n",
    "            r = candies - n * (n+1)//2\n",
    "        l = list(range(1, n + 1))\n",
    "        if r > 0:\n",
    "            l.append(r)\n",
    "        for i, c in enumerate(l):\n",
    "            ans[i  % num_people ]+=c\n",
    "        return ans \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "                          i=1\n",
    "                          a=[]\n",
    "                          b=[0]*num_people                          \n",
    "                          while candies>0 :\n",
    "                             if candies-i>=0:\n",
    "                                a.append(i)\n",
    "                                candies=candies-i\n",
    "                                i=i+1\n",
    "                             else:\n",
    "                                 a.append(candies)\n",
    "                                 candies=candies-i\n",
    "                          for i in range(len(a)):\n",
    "                                 b[i%num_people]=b[i%num_people]+a[i]\n",
    "                          return b\n",
    "                               \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        li = []\n",
    "        res = [0]*num_people\n",
    "        candy = 1\n",
    "        i = candies\n",
    "        while i >= candy:\n",
    "            li.append(candy)\n",
    "            i -= candy\n",
    "            candy += 1\n",
    "        li.append(i)\n",
    "        for i in range(len(li)):\n",
    "            a = i % num_people\n",
    "            res[a] += li[i]\n",
    "        return res\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        n_list = []\n",
    "        for i in range(1, candies):\n",
    "            if candies > i:\n",
    "                n_list.append(i)\n",
    "                candies -= i\n",
    "            else:\n",
    "                n_list.append(candies)\n",
    "                break\n",
    "        s_list = []\n",
    "        for i in range(num_people):\n",
    "            sum_n = 0\n",
    "            for j in range(i, len(n_list), num_people):\n",
    "                sum_n += n_list[j]\n",
    "            s_list.append(sum_n)\n",
    "        return s_list\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "\n",
    "        out = list()\n",
    "\n",
    "        i = 1\n",
    "\n",
    "        while candies > 0:\n",
    "            a = min(candies,i)\n",
    "            out.append(a)\n",
    "\n",
    "            i += 1\n",
    "            candies -= a\n",
    "\n",
    "        output = [0 for i in range(num_people)]\n",
    "\n",
    "        for i in range(num_people):\n",
    "            for j in range(i,len(out),num_people):\n",
    "                output[i] += out[j]\n",
    "        return output\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        result = []\n",
    "        n = 1\n",
    "        while candies > 0:\n",
    "            if n <= candies:\n",
    "                result.append(n)\n",
    "            else:\n",
    "                result.append(candies)\n",
    "            candies = candies - n\n",
    "            n += 1\n",
    "        use_l = len(result)\n",
    "        if use_l < num_people:\n",
    "            result = result + [0] * (num_people - use_l)\n",
    "        else:\n",
    "            for i in range(num_people):\n",
    "                result[i] = sum(result[i::num_people])\n",
    "            result = result[:num_people]\n",
    "\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "       i=0\n",
    "       sum = 0\n",
    "       ans=[]\n",
    "       while sum<=candies:\n",
    "           i+=1\n",
    "           ans.append(i)\n",
    "           sum+=i\n",
    "       m=candies-(sum-ans[-1])\n",
    "       ans.pop()\n",
    "       ans.append(m)\n",
    "       ans1=[0]*num_people\n",
    "       for i in range(0,len(ans)):\n",
    "           ans1[((i+1)%num_people)-1] += ans[i] \n",
    "       return ans1 \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int):\n",
    "        lst = [1]\n",
    "        res = []\n",
    "        for i in range(2, candies):\n",
    "            if sum(lst) + i < candies:\n",
    "                lst.append(i)\n",
    "            else:\n",
    "                lst.append(candies - sum(lst))\n",
    "                break\n",
    "        for i in range(num_people):\n",
    "            sums = 0\n",
    "            for j in range(i, len(lst), num_people):\n",
    "                sums += lst[j]\n",
    "            res.append(sums)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        kids = [0] * num_people\n",
    "        dp = [1]\n",
    "        candies -= 1\n",
    "        while candies > 0:\n",
    "            curr = dp[-1] + 1\n",
    "            if candies >= curr:\n",
    "                candies -= curr\n",
    "                dp.append(curr)\n",
    "            else:\n",
    "                dp.append(candies)\n",
    "                candies = 0\n",
    "        for i in range(len(dp)):\n",
    "            kids[i%num_people] += dp[i]\n",
    "        return kids\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        a = 1\n",
    "        list1 = []\n",
    "        while candies>a:\n",
    "            list1.append(a)\n",
    "            candies-=a\n",
    "            a+=1\n",
    "        list1.append(candies)\n",
    "\n",
    "        list2 = []\n",
    "        for i in range(num_people):\n",
    "            list2.append(sum(list1[i::num_people]))\n",
    "        return list2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        l = []\n",
    "        i = 1\n",
    "        while candies > 0:\n",
    "            l.append(i)\n",
    "            candies -= i\n",
    "            i += 1\n",
    "        l[-1] += candies\n",
    "        res = [0] * num_people\n",
    "        for i in range(num_people):\n",
    "            res[i] = sum(l[i::num_people])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        l = []\n",
    "        i = 1\n",
    "        while candies > 0:\n",
    "            l.append(i)\n",
    "            candies -= i\n",
    "            i += 1\n",
    "        l[-1] += candies\n",
    "        res = [0] * num_people\n",
    "        for i in range(num_people):\n",
    "            res[i] = sum(l[i::num_people])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        l = []\n",
    "        i = 1\n",
    "        while candies > 0:\n",
    "            l.append(i)\n",
    "            candies -= i\n",
    "            i += 1\n",
    "        l[-1] += candies\n",
    "        res = [0] * num_people\n",
    "        for i in range(num_people):\n",
    "            res[i] = sum(l[i::num_people])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        for i in range(int((2*candies)**0.5)+2,-1,-1):\n",
    "            if i*(i+1)//2 <=candies<=(i+1)*(i+2)//2:\n",
    "                s = i\n",
    "        b = candies-s*(s+1)//2\n",
    "        num = [i for i in range(1,s+1)] +[b]\n",
    "        result = [0]*num_people\n",
    "        for j in range(len(num)):\n",
    "            m = j%num_people\n",
    "            result[m] += num[j]\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        n = 1\n",
    "        while n * (n + 1) / 2 < candies:\n",
    "            n += 1\n",
    "        candies_lst = [i for i in range(1, n)] + [candies - n * (n - 1) // 2]\n",
    "        res = []\n",
    "        for i in range(num_people):\n",
    "            res.append(sum(candies_lst[i::num_people]))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        arr_can = []\n",
    "        # the candies num we give to every person\n",
    "        use_can = 1\n",
    "        # remain candies\n",
    "        re_can = candies\n",
    "        # result\n",
    "        res = [0] * num_people\n",
    "        while re_can > use_can:\n",
    "            # when we have candies to give\n",
    "            re_can = re_can - use_can\n",
    "            arr_can.append(use_can)\n",
    "            use_can += 1\n",
    "            # debug cmd\n",
    "        # last person receive all remaining candies\n",
    "        arr_can.append(re_can)\n",
    "        # debug cmd\n",
    "        print(arr_can)\n",
    "        num_give = int(len(arr_can)/num_people) + 1\n",
    "        # compute the complete give candies two-dimensional array\n",
    "        all_give = num_give * num_people\n",
    "        arr_can = arr_can + [0] * (all_give - len(arr_can))\n",
    "        # compute the candies that every person receive\n",
    "        for i in range(num_people):\n",
    "            # the turn we give candies, start from 0\n",
    "            give = 0\n",
    "            while give < num_give:\n",
    "                res[i] += arr_can[i+give*num_people]\n",
    "                give += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        data = []\n",
    "        for i in range(1,candies):\n",
    "            data.append(i)\n",
    "            if sum(data)> candies:\n",
    "                data.pop()\n",
    "                break\n",
    "        last = candies - sum(data)\n",
    "        data.append(last)\n",
    "        print('last:',data)\n",
    "        group = []\n",
    "        for i in range(0,len(data),num_people):\n",
    "            group.append(data[i:i+num_people])\n",
    "        if len(group[-1]) != num_people:\n",
    "            for i in range(num_people - len(group[-1])):\n",
    "                group[-1].append(0)\n",
    "        result = []\n",
    "        for i in list(zip(*group)):\n",
    "            result.append(sum(i))\n",
    "        return result \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        n=0\n",
    "        while n*(n+1)/2<candies:\n",
    "            n+=1\n",
    "        res=[0]*n\n",
    "        for i in range(n-1):\n",
    "            res[i]=i+1\n",
    "        res[n-1]=int(candies-(n-1)*n/2)\n",
    "        result=[0]*num_people\n",
    "        print(res)\n",
    "        for i,value in enumerate(res):\n",
    "            index=i\n",
    "            while index >=num_people:\n",
    "                index-=num_people\n",
    "            result[index]+=value\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        i = 0\n",
    "        #计算有多少个元素\n",
    "        while True:\n",
    "            tmp = i ** 2 + i\n",
    "            if tmp >= 2 * candies:\n",
    "                break\n",
    "            i += 1\n",
    "        m, n = divmod(i, num_people)#有n+1行，最后剩n个元素，如果n不为0，则有m + 2行\n",
    "        if n != 0:\n",
    "            m += 1\n",
    "        li_w = []\n",
    "        total = 0\n",
    "        for k in range(m):\n",
    "            li = []\n",
    "            for j in range(num_people):\n",
    "                total += num_people*k + 1 + j\n",
    "                if total >= candies:\n",
    "                    li.append(num_people*k + 1 + j + candies - total)\n",
    "                    if j < num_people - 1:\n",
    "                        for k in range(num_people - 1 - j):\n",
    "                            li.append(0)\n",
    "                    break\n",
    "                else:\n",
    "                    li.append(num_people*k + 1 + j)\n",
    "            li_w.append(li)\n",
    "        li_t = [0]*num_people\n",
    "\n",
    "        for x in range(num_people):\n",
    "            tmp = 0\n",
    "            for y in range(m):\n",
    "                tmp += li_w[y][x]\n",
    "            li_t[x] = tmp\n",
    "\n",
    "        return li_t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        list_candy = []\n",
    "        candy_consum = 1\n",
    "        outcome = []\n",
    "        while candies - candy_consum > 0:\n",
    "            list_candy.append(candy_consum)\n",
    "            candies -= candy_consum\n",
    "            candy_consum += 1\n",
    "        list_candy.append(candies)\n",
    "        times = len(list_candy)/num_people\n",
    "        for i in range(num_people):\n",
    "            outcome.append(0)\n",
    "        if int(times) != times:\n",
    "            times = int(times) + 1\n",
    "        else:\n",
    "            times = int(times)\n",
    "        for i in range(times):\n",
    "            for j in range(num_people):\n",
    "                if i * num_people + j <= len(list_candy) - 1:\n",
    "                    outcome[j] += list_candy[i*num_people+j]\n",
    "                else: break\n",
    "        return outcome\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "\n",
    "        sum1 = 0\n",
    "        ans, res = [], [0 for _ in range(num_people)]\n",
    "\n",
    "        for i in range(1, candies):\n",
    "            sum1 += i\n",
    "  \n",
    "            if sum1 >= candies:\n",
    "                ans.append(candies - sum1 + i)\n",
    "            else:\n",
    "                ans.append(i)\n",
    "\n",
    "            res[(i - 1) % num_people] += ans[i - 1]\n",
    "            \n",
    "            if sum1 >= candies:\n",
    "                break\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "\n",
    "        sum1 = 0\n",
    "        ans, res = [], [0 for _ in range(num_people)]\n",
    "\n",
    "        for i in range(1, candies):\n",
    "            sum1 += i\n",
    "  \n",
    "            if sum1 >= candies:\n",
    "                ans.append(candies - sum1 + i)\n",
    "            else:\n",
    "                ans.append(i)\n",
    "\n",
    "            res[(i - 1) % num_people] += ans[i - 1]\n",
    "            \n",
    "            if sum1 >= candies:\n",
    "                break\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        allocate = []\n",
    "        cnt = 1\n",
    "        sums = 1\n",
    "        while sums <= candies:\n",
    "            allocate.append(cnt)            \n",
    "            cnt += 1\n",
    "            sums += cnt\n",
    "        allocate.append(cnt + candies - sums)\n",
    "        res = [0] * num_people\n",
    "        for i in range(len(allocate)):\n",
    "            res[i % num_people] += allocate[i]\n",
    "        return res\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "\n",
    "        sum1 = 0\n",
    "        ans, res = [], [0 for _ in range(num_people)]\n",
    "\n",
    "        for i in range(1, candies):\n",
    "            sum1 += i\n",
    "  \n",
    "            if sum1 >= candies:\n",
    "                ans.append(candies - sum1 + i)\n",
    "            else:\n",
    "                ans.append(i)\n",
    "\n",
    "            res[(i - 1) % num_people] += ans[i - 1]\n",
    "            \n",
    "            if sum1 >= candies:\n",
    "                break\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candyType: List[int]) -> int:\n",
    "        candyType= sorted(candyType)\n",
    "        seq=1\n",
    "        for i in range(1,len(candyType)):\n",
    "            if candyType[i-1]!=candyType[i]:\n",
    "                seq+=1\n",
    "        return min(seq, len(candyType) // 2)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candyType: List[int]) -> int:\n",
    "        cnt_dic = {} # 每个数字出现的次数\n",
    "        only_one_type = set()\n",
    "        for each in candyType:\n",
    "            if each in cnt_dic: \n",
    "                only_one_type.discard(each)\n",
    "                cnt_dic[each] = cnt_dic[each]+1\n",
    "            else:\n",
    "                only_one_type.add(each)\n",
    "                cnt_dic[each] = 1\n",
    "        for each_key in list(cnt_dic.keys()):\n",
    "            if each_key in only_one_type:\n",
    "                cnt_dic.pop(each_key)\n",
    "        half_arr = int(len(candyType)/2)  # 一半长度\n",
    "\n",
    "        if len(only_one_type) >= half_arr:\n",
    "            # 单独类型的够多，给妹妹全部单独类型\n",
    "            return half_arr\n",
    "        \n",
    "        return int(len(only_one_type) + len(cnt_dic)) if len(only_one_type) + len(cnt_dic) <= half_arr else half_arr\n",
    "        \n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candyType: List[int]) -> int:\n",
    "        n = len(candyType)\n",
    "        a = int(n/2)\n",
    "        c = 1\n",
    "        candyType.sort()\n",
    "        for i in range(1,n):\n",
    "            if candyType[i] != candyType[i-1]:\n",
    "                c+=1\n",
    "        if c > a: return a\n",
    "        else: return c\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candyType: List[int]) -> int:\n",
    "        candyType = sorted(candyType)\n",
    "        j = 1\n",
    "        for i in range(1, len(candyType)):\n",
    "            if candyType[i] != candyType[i-1]:\n",
    "                j += 1\n",
    "        return min(j, len(candyType)//2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candyType: List[int]) -> int:\n",
    "        count = 1\n",
    "        n = len(candyType)\n",
    "        candyType.sort()\n",
    "        for i in range(0, n - 1):\n",
    "            if candyType[i + 1] != candyType[i]: \n",
    "                count += 1\n",
    "            if count >= n//2: \n",
    "                return n//2\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candyType: List[int]) -> int:\n",
    "        candynum = len(candyType)\n",
    "        candyType = sorted(candyType)\n",
    "        candy = candyType[0]\n",
    "        typenum = 1\n",
    "        for i in range(1, candynum):\n",
    "            if candy != candyType[i]:\n",
    "                candy = candyType[i]\n",
    "                typenum += 1\n",
    "        return min(typenum, candynum//2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candyType: List[int]) -> int:\n",
    "        cnt = 0\n",
    "        candyType.sort()\n",
    "        for i, v in enumerate(candyType):\n",
    "            if i == 0 or v != candyType[i-1]:\n",
    "                cnt += 1\n",
    "        \n",
    "        return cnt if len(candyType)//2 >= cnt else len(candyType)//2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candyType: List[int]) -> int:\n",
    "        s=0\n",
    "        f=1\n",
    "        n=len(candyType)\n",
    "        candyType.sort()\n",
    "        while f<n:\n",
    "            if candyType[f]!=candyType[s]:\n",
    "                candyType[s+1]=candyType[f]\n",
    "                s+=1\n",
    "            f+=1\n",
    "        candyType=candyType[:s+1:]\n",
    "        return s+1 if s+1<=n/2 else int(n/2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candyType: List[int]) -> int:\n",
    "        n=len(candyType)\n",
    "        candyType.sort()\n",
    "        eat_candy=1\n",
    "        ans=0\n",
    "        for i in range(1,n):\n",
    "            if eat_candy<n/2:\n",
    "                if candyType[i]!=candyType[i-1]:\n",
    "                    eat_candy+=1\n",
    "                    ans+=1\n",
    "                    continue\n",
    "            else:\n",
    "                return ans+1\n",
    "        return ans+1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candyType: List[int]) -> int:\n",
    "        cadylist = []\n",
    "        for i in candyType:\n",
    "            if i not in cadylist:\n",
    "                cadylist.append(i)\n",
    "            if len(cadylist) == len(candyType) / 2:\n",
    "                return round(len(candyType) / 2)\n",
    "        \n",
    "        return round(len(cadylist))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candyType: List[int]) -> int:\n",
    "        t = 1\n",
    "        candyType.sort()\n",
    "        for i in range(1,len(candyType)):\n",
    "            if candyType[i] != candyType[i - 1]:\n",
    "                t += 1\n",
    "        if t >= len(candyType) / 2:\n",
    "            return int(len(candyType) / 2)\n",
    "        else:\n",
    "            return t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candyType: List[int]) -> int:\n",
    "        n = len(candyType)\n",
    "        candyType.sort()\n",
    "        i = 1\n",
    "        while i < len(candyType):\n",
    "            if candyType[i] == candyType[i-1]:\n",
    "                candyType.pop(i)\n",
    "            else:\n",
    "                i += 1\n",
    "        \n",
    "        return int(min(len(candyType), n / 2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candyType: List[int]) -> int:\n",
    "        list1 = candyType\n",
    "        list2 = []\n",
    "        n = len(list1) / 2\n",
    "        for item in list1:\n",
    "            if item not in list2:\n",
    "                list2.append(item)\n",
    "                if len(list2) == n:\n",
    "                    break\n",
    "        return len(list2)   \n",
    "\n",
    "\n",
    "solution = Solution()\n",
    "candyType = [1,1,2,3, 6, 6]\n",
    "print(solution.distributeCandies(candyType))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candyType: List[int]) -> int:\n",
    "        allow = len(candyType) // 2\n",
    "        types = 0\n",
    "        candyType.sort()\n",
    "        for i, val in enumerate(candyType):\n",
    "            if i > 0 and val == candyType[i - 1]:\n",
    "                continue\n",
    "            if allow == 0:\n",
    "                break\n",
    "            allow -= 1\n",
    "            types += 1\n",
    "        return types\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candyType: List[int]) -> int:\n",
    "        #按照不同种类糖的数量排序从小到大\n",
    "        data_dict = {}\n",
    "        for i in candyType:\n",
    "            if i not in data_dict:\n",
    "                data_dict[i] = 1\n",
    "            else:\n",
    "                data_dict[i] += 1\n",
    "        data = data_dict.items()\n",
    "        sorted(data,key = lambda x:x[1])\n",
    "        N_sample = 0\n",
    "        n = len(candyType) // 2\n",
    "        m = 0 \n",
    "        for x in data:\n",
    "            m += 1\n",
    "            N_sample += 1\n",
    "            if m >= n:\n",
    "                break\n",
    "            \n",
    "        return N_sample\n",
    "            \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candyType: List[int]) -> int:\n",
    "        diction = {}\n",
    "        lens = 0\n",
    "        for i in candyType:\n",
    "            if i not in diction:\n",
    "                lens += 1\n",
    "                diction[i] = 1\n",
    "            if lens >= len(candyType) // 2:\n",
    "                return len(candyType) // 2\n",
    "        return min(lens, len(candyType) // 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candyType: List[int]) -> int:\n",
    "        candyType.sort()\n",
    "        n = len(candyType)\n",
    "        cnt = 1\n",
    "        idx = 1\n",
    "        while cnt < n // 2 and idx < n:\n",
    "            while idx < n and candyType[idx] == candyType[idx-1]:\n",
    "                idx += 1\n",
    "            if idx < n: cnt += 1\n",
    "            idx += 1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candyType: List[int]) -> int:\n",
    "        n = len(candyType)\n",
    "        d = defaultdict(int)\n",
    "        count = 0\n",
    "        for candy in candyType:\n",
    "            if d[candy] == 0:\n",
    "                d[candy] = 1\n",
    "                count += 1\n",
    "                if count == n//2:\n",
    "                    return count\n",
    "        return count\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candyType: List[int]) -> int:\n",
    "        can = len(candyType) / 2\n",
    "        newtype = []\n",
    "        n = 0\n",
    "        for i in candyType:\n",
    "            if i not in newtype:\n",
    "                newtype.append(i)\n",
    "                n += 1\n",
    "            if n >= can:\n",
    "                return n\n",
    "        return n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candyType: List[int]) -> int:\n",
    "        n = len(candyType)\n",
    "        candyType.sort()\n",
    "        types = [candyType[0]]\n",
    "        for i in range(1, n):\n",
    "            if candyType[i] == candyType[i-1]:\n",
    "                continue\n",
    "            else:\n",
    "                types.append(candyType[i])\n",
    "        return min(n//2, len(types))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import OrderedDict\n",
    "class Solution:\n",
    "    def distributeCandies(self, candyType: List[int]) -> int:\n",
    "        queuedict=dict()\n",
    "        types=0\n",
    "        n=len(candyType)//2\n",
    "        for i in candyType:\n",
    "            if n==0:\n",
    "                return types\n",
    "            if i in queuedict:\n",
    "                continue\n",
    "            else:\n",
    "                queuedict[i]=1\n",
    "                types+=1\n",
    "                n-=1\n",
    "        return types\n",
    "        # sorted(queuedict.items(),key=lambda x:x[1])\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candyType: List[int]) -> int:\n",
    "        res = []\n",
    "        cnt = 0\n",
    "        for i in range(len(candyType)):\n",
    "            if candyType[i] not in res:\n",
    "                res.append(candyType[i])\n",
    "                cnt = cnt + 1\n",
    "                if cnt == len(candyType)/2:\n",
    "                    return cnt\n",
    "                \n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candyType: List[int]) -> int:\n",
    "        m=candyType\n",
    "        m=sorted(m)\n",
    "        n=len(m)\n",
    "        l=n/2\n",
    "        if n==2:\n",
    "            return 1\n",
    "        else:\n",
    "            k=1\n",
    "            for i in range(n-1):\n",
    "                if m[i]!=m[i+1]:\n",
    "                    k=k+1\n",
    "            if k<=l:\n",
    "                return k\n",
    "            else:\n",
    "                return int(l)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candyType: List[int]) -> int:\n",
    "        candynum = len(candyType)\n",
    "        candydict = dict()\n",
    "        typenum = 0\n",
    "        for candy in candyType:\n",
    "            if candy not in candydict:\n",
    "                candydict[candy] = 1\n",
    "                typenum += 1\n",
    "                if typenum == candynum//2:\n",
    "                    break\n",
    "        return typenum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candyType: List[int]) -> int:\n",
    "        candyType.sort()\n",
    "        n = len(candyType)\n",
    "        a = 1\n",
    "        for i in range(n-1):\n",
    "            if candyType[i+1] != candyType[i]:\n",
    "                a += 1\n",
    "        return int(min(a,n/2))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candyType: List[int]) -> int:\n",
    "        n = len(candyType)\n",
    "        num = 1\n",
    "        candyType.sort()\n",
    "        k = candyType[0]\n",
    "        for i in range(1,n):\n",
    "            if candyType[i]>k:\n",
    "                num +=1\n",
    "                k = candyType[i]\n",
    "        if num > n/2:\n",
    "            return n // 2\n",
    "        else :\n",
    "            return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candyType: List[int]) -> int:\n",
    "        m=candyType\n",
    "        m=sorted(m)\n",
    "        n=len(m)\n",
    "        l=n/2\n",
    "        k=1\n",
    "        for i in range(n-1):\n",
    "            if m[i]!=m[i+1]:\n",
    "                k=k+1\n",
    "        if k<=l:\n",
    "            return k\n",
    "        else:\n",
    "            return int(l)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candyType: List[int]) -> int:\n",
    "        candyTypeKey = {}\n",
    "        for i in candyType:\n",
    "            if i not in candyTypeKey:\n",
    "                candyTypeKey[i] = 1\n",
    "            else:\n",
    "                candyTypeKey[i] += 1\n",
    "        candyTypeKey = sorted(candyTypeKey.items(), key=lambda kv: (kv[1], kv[0]))\n",
    "        sisterCandies = []\n",
    "        for l in candyTypeKey:\n",
    "            if l[0] not in sisterCandies:\n",
    "                sisterCandies.append(l[0])\n",
    "            if len(sisterCandies) == len(candyType) / 2:\n",
    "                break\n",
    "        return len(sisterCandies)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candyType: List[int]) -> int:\n",
    "        \n",
    "        n = len(candyType)\n",
    "        \n",
    "        data = dict(collections.Counter(candyType))\n",
    "        data = [(k,v) for k,v in data.items()]\n",
    "        data.sort(key = lambda x:x[1])\n",
    "        \n",
    "        target = 0\n",
    "        for t,num in data:\n",
    "            if target<n//2:\n",
    "                target +=1\n",
    "            else:\n",
    "                break\n",
    "        \n",
    "        return target"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candyType: List[int]) -> int:\n",
    "        temp=collections.Counter(candyType)\n",
    "        type_num=len(temp.items())#有多少种糖\n",
    "        x=len(candyType)//2#最多能吃多少颗糖\n",
    "        result=0\n",
    "        if x<=type_num:\n",
    "            result=x\n",
    "            return result\n",
    "        return type_num\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candyType: List[int]) -> int:\n",
    "        record = {}\n",
    "        for num in candyType:\n",
    "            if num not in record:\n",
    "                record[num] = True\n",
    "                if len(record) >= len(candyType) // 2:\n",
    "                    return len(candyType) // 2\n",
    "        \n",
    "        return len(record)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candyType: List[int]) -> int:\n",
    "        candynum = len(candyType)\n",
    "        candydict = dict()\n",
    "        typenum = 0\n",
    "        for candy in candyType:\n",
    "            if candy not in candydict:\n",
    "                candydict[candy] = 1\n",
    "                typenum += 1\n",
    "        return min(typenum, candynum//2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candyType: List[int]) -> int:\n",
    "        HashMap = {}\n",
    "        for i in candyType:\n",
    "            if i not in HashMap.keys():\n",
    "                HashMap[i] = 1\n",
    "            else:\n",
    "                HashMap[i] += 1\n",
    "        return min(len(HashMap),len(candyType)//2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candyType: List[int]) -> int:\n",
    "        n = len(candyType) // 2\n",
    "        c = Counter(candyType)\n",
    "        ans = min(len(c), n)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candyType: List[int]) -> int:\n",
    "        dic = {}\n",
    "        for n in candyType:\n",
    "            dic[n] = 1\n",
    "        return len(dic) if len(candyType)//2 >= len(dic) else len(candyType)//2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candyType: List[int]) -> int:\n",
    "        n = len(candyType) // 2\n",
    "        candys = {}\n",
    "        for i in candyType:\n",
    "            if i not in candys:\n",
    "               candys[i] = 1\n",
    "            else:\n",
    "                candys[i] += 1\n",
    "        count = len(candys)\n",
    "        if(count == 1):\n",
    "            return 1\n",
    "        if(n < count):\n",
    "            return n\n",
    "        elif(n > count):\n",
    "            return count\n",
    "        else:\n",
    "            return count\n",
    "            \n",
    "        \n",
    "         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candyType: List[int]) -> int:\n",
    "        dic = {}\n",
    "        for i in candyType:\n",
    "            if i not in dic:\n",
    "                dic[i] = 1\n",
    "        return min(len(dic.items()),len(candyType)//2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candyType: List[int]) -> int:\n",
    "        candyType_Counter = Counter(candyType)\n",
    "        candyType_count = len(candyType)\n",
    "        candyType_keys_Counter = len(candyType_Counter.keys())\n",
    "        if len(candyType)//2 <= candyType_keys_Counter:\n",
    "            return len(candyType)//2\n",
    "        else:\n",
    "            return candyType_keys_Counter"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candyType: List[int]) -> int:\n",
    "        return min(len(Counter(candyType)), len(candyType)//2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candyType: List[int]) -> int:\n",
    "        c = Counter(candyType)\n",
    "        return min(len(c),len(candyType)//2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candyType: List[int]) -> int:\n",
    "        c = Counter(candyType)\n",
    "        return len(candyType) // 2 if len(candyType) // 2 < len(c) else len(c)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candyType: List[int]) -> int:\n",
    "      types = len(set(candyType))\n",
    "      n = len(candyType)//2\n",
    "      res = 0\n",
    "      res = min(types, n)\n",
    "      return res\n",
    "      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candyType: List[int]) -> int:\n",
    "        n=len(candyType)\n",
    "        eat_num=n//2\n",
    "        c=collections.Counter(candyType)\n",
    "        if len(c)>eat_num:\n",
    "            return eat_num\n",
    "        else:\n",
    "            return len(c)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candyType: List[int]) -> int:\n",
    "        n = len(candyType)\n",
    "        cnt = collections.Counter(candyType)\n",
    "        \n",
    "        cat = len(cnt)\n",
    "        return min(n//2, cat)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candyType: List[int]) -> int:\n",
    "        CanEat = int(len(candyType)/2)  #能吃糖的数量\n",
    "        dic = {}\n",
    "        for candy in candyType:\n",
    "            if candy not in dic:\n",
    "                dic[candy] = 1\n",
    "            else:\n",
    "                dic[candy] += 1\n",
    "        return len(dic) if len(dic) <= CanEat else CanEat\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candyType: List[int]) -> int:\n",
    "        m = len(candyType)//2\n",
    "        # candyset = set(candyType)\n",
    "        candyset = set()\n",
    "        for c in candyType:\n",
    "            candyset.add(c)\n",
    "        return min(m, len(candyset))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candyType: List[int]) -> int:\n",
    "        n = len(candyType)\n",
    "        s = set()\n",
    "        for item in candyType:\n",
    "            if item in s:\n",
    "                pass\n",
    "            else:\n",
    "                s.add(item)\n",
    "        return min(n // 2, len(s))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candyType: List[int]) -> int:\n",
    "        m={}\n",
    "        for i in candyType:\n",
    "            if i in m:\n",
    "                m[i]+=1\n",
    "            else:\n",
    "                m[i]=1\n",
    "        if (len(candyType)/2)>=len(m):\n",
    "            return len(m)\n",
    "        else:\n",
    "            return int(len(candyType)/2)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candyType: List[int]) -> int:\n",
    "        n = len(candyType)\n",
    "        total = n // 2\n",
    "        freq = Counter(candyType)\n",
    "        return min(len(freq), total)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candyType: List[int]) -> int:\n",
    "        m={}\n",
    "        for i in candyType:\n",
    "            if i in m:\n",
    "                m[i]+=1\n",
    "            else:\n",
    "                m[i]=1\n",
    "        if (len(candyType)/2)>=len(m):\n",
    "            return len(m)\n",
    "        else:\n",
    "            return int(len(candyType)/2)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candyType: List[int]) -> int:\n",
    "        n = len(candyType)//2\n",
    "        temp = len(set(candyType))\n",
    "        return min(n, temp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candyType: List[int]) -> int:\n",
    "        return min(len(set(candyType)), len(candyType)//2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candyType: List[int]) -> int:\n",
    "        return min(len(set(candyType)), len(candyType)//2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candyType: List[int]) -> int:\n",
    "        return min(len(set(candyType)), len(candyType)//2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import itertools\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candyType: List[int]) -> int:\n",
    "        x = len(candyType) // 2\n",
    "        set_len = len(set(candyType))\n",
    "        if set_len >= x:\n",
    "            return x\n",
    "        return set_len\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candyType: List[int]) -> int:\n",
    "        n = len(candyType) / 2;\n",
    "        return min(int(n),len(set(candyType)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candyType: List[int]) -> int:\n",
    "        unique_lens = len(set(candyType))\n",
    "        n = int(len(candyType)/2)\n",
    "        if n<=unique_lens:\n",
    "            return n\n",
    "        else:\n",
    "            return unique_lens"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candyType: List[int]) -> int:\n",
    "        return int(min(len(candyType) / 2 ,len(set(candyType))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candyType: List[int]) -> int:\n",
    "        nums=set(candyType)\n",
    "        n=len(candyType)\n",
    "        m=len(nums)\n",
    "        x=n//2\n",
    "        if x>=m:\n",
    "            return m\n",
    "        else:\n",
    "            return x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def distributeCandies(self, candyType: List[int]) -> int:\r\n",
    "        n = len(candyType)\r\n",
    "        d = {}\r\n",
    "        res = n // 2\r\n",
    "        \r\n",
    "        for i in candyType:\r\n",
    "            if i in d:\r\n",
    "                d[i] += 1\r\n",
    "                n -= 1\r\n",
    "            else:\r\n",
    "                d[i] = 1\r\n",
    "        return res if res < n  else n\r\n",
    "        # n = len(candyType)\r\n",
    "        # return n // 2 if n // 2 < len(set(candyType)) else len(set(candyType))\r\n",
    "        \r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candyType: List[int]) -> int:\n",
    "        cat = len(set(candyType))\n",
    "        return min(len(candyType)//2, cat)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candyType: List[int]) -> int:\n",
    "        return min(len(set(candyType)), len(candyType) // 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candyType: List[int]) -> int:\n",
    "        candySet = list(set(candyType))\n",
    "        return min(len(candyType)//2,len(candySet))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candyType: List[int]) -> int:\n",
    "        return min(len(candyType)//2, len(list(set(candyType))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candyType: List[int]) -> int:\n",
    "        return len(candyType)//2 if len(candyType)//2<len(set(candyType)) else len(set(candyType))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candyType: List[int]) -> int:\n",
    "        return min(len(candyType)//2,len(set(candyType)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candyType: List[int]) -> int:\n",
    "        return len(set(candyType)) if len(candyType) // 2 > len(set(candyType)) else len(candyType) // 2 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candyType: List[int]) -> int:\n",
    "        m = len(candyType)\n",
    "        n = len(set(candyType))\n",
    "        if n >= int(m/2):\n",
    "            return int(m/2)\n",
    "        else :\n",
    "            return n\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candyType: List[int]) -> int:\n",
    "        return min(len(set(candyType)),len(candyType)//2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candyType: List[int]) -> int:\n",
    "        n = len(candyType)\n",
    "        candy = set(candyType)\n",
    "        cnt = len(candy)\n",
    "        if n // 2 >= cnt:\n",
    "            return cnt\n",
    "        else:\n",
    "            return n // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candyType: List[int]) -> int:\n",
    "        n=len(candyType)\n",
    "        hh=len(list(set(candyType)))\n",
    "        return min(n//2,hh)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candyType: List[int]) -> int:\n",
    "        # 我的思路:\n",
    "        # 找到candytype最多的种类,和n/2取最小值\n",
    "        res = len(set(candyType))\n",
    "        n = int(len(candyType)/2)\n",
    "        return min(res,n)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candyType: List[int]) -> int:\n",
    "        k=len(set(candyType))\n",
    "        m=int(len(candyType)/2)\n",
    "\n",
    "        if k<=m: return k\n",
    "        if k>m: return m\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candyType: List[int]) -> int:\n",
    "        candy_type = set(candyType)\n",
    "        return min(len(candy_type),len(candyType)//2)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candyType: List[int]) -> int:\n",
    "        # 糖果种类大于糖的一半，最多分\n",
    "        return min(len(set(candyType)), len(candyType)//2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candyType: List[int]) -> int:\n",
    "        return min(len(candyType)//2, len(list(set(candyType))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candyType: List[int]) -> int:\n",
    "        s = list(set(candyType))\n",
    "        n=len(candyType)\n",
    "        if(len(s)>n/2):\n",
    "            return int(n/2)\n",
    "        else:\n",
    "            return len(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def distributeCandies(self, candyType: List[int]) -> int:\r\n",
    "        # n = len(candyType)\r\n",
    "        # d = {}\r\n",
    "        # res = n // 2\r\n",
    "        \r\n",
    "        # for i in candyType:\r\n",
    "        #     if i in d:\r\n",
    "        #         d[i] += 1\r\n",
    "        #         n -= 1\r\n",
    "        #     else:\r\n",
    "        #         d[i] = 1\r\n",
    "        # return max(res, n)\r\n",
    "        n = len(candyType)\r\n",
    "        return n // 2 if n // 2 < len(set(candyType)) else len(set(candyType))\r\n",
    "        \r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candyType: List[int]) -> int:\n",
    "        a=int(len(set(candyType)))\n",
    "        b=int(len(candyType)/2)\n",
    "        if b<=a:\n",
    "            return b\n",
    "        else:\n",
    "            return a\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
